#include <fstream>
#include <string>
#include <sstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <ctime>
#include <cstdlib>
#include "network.h"

/* CLASS SCOPE CONSTANTS */

const int network::SUCCESS = 0, network::FILE_NOT_VALID = 1, network::FILE_NOT_OPEN = 2, network::PARSE_ERROR = 3;
const int network::POINT_POINT = 0, network::POINT_RPOINT =1, network::LINKTABLE_TAIL = 0, network::LINKTABLE_HEAD = 1, network::LINKTABLE_TRACE = 2, network::CAPTABLE_COST = 0, network::CAPTABLE_CAP = 1, network::CAPTABLE_INST1 = 2, network::CAPTABLE_PRICE1 = 3;
const int network::DOES_NOT_EXIST = -1, network::NOT_DEFINED = -2;



/* CONSTRUCTORS */

network::network() {
  point = std::vector< std::vector<int> >(0, std::vector<int>(0, 2));
  linktable = std::vector< std::vector<int> >(0, std::vector<int>(0, 3));
  capacitytable = std::vector < std::vector<double> >(0, std::vector<double>(0,4));
  nodenr = std::map<std::string, int>();
  linknr = std::map<std::string, int>();
  nodeid = std::vector<std::string>(0);
  linkid = std::vector<std::string>(0);
  demands = std::vector< std::vector<double> >(0, std::vector<double>(0));
}

network::network(std::string path) {
  read_network_file(path);
}


/* FILE ACCESS MEMBER FUNCTIONS */

// read_network_file reads a SNDlib network file and stores the data in the object.

bool network::readline(std::ifstream &input, std::string &read_to) {
  getline(input, read_to);
  int ii = read_to.find_first_not_of(' ');
  if (ii == std::string::npos || read_to[ii] == '#')
    return false;
  read_to = read_to.substr(ii, read_to.size());
  return true;
}

int network::read_network_file(std::string path) {
  int retval;
  std::ifstream netfile;
  netfile.open(path.data(), std::ifstream::in);
  retval = read_network_file(netfile);
  netfile.close();
  return retval;
}

int network::read_network_file(std::ifstream &netfile) {
  std::string line;
  bool validline;
  int retval = network::SUCCESS;

  if(!netfile.is_open()) {
    return network::FILE_NOT_OPEN;
  }
  getline(netfile, line);
  if(line.substr(0,52).compare("?SNDlib native format; type: network; version: 1.0") != 0) {
    return network::FILE_NOT_VALID;
  }

  while (netfile.good()) {
    validline = readline(netfile, line);
    if(!validline)
      continue;
    else if(line.substr(0, 7).compare("NODES (") == 0)
      retval = readnodes(netfile);
    else if(line.substr(0, 7).compare("LINKS (") == 0)
      retval = readlinks(netfile);
    else if(line.substr(0, 9).compare("DEMANDS (") == 0)
      retval = readdemands(netfile);
    if(retval != SUCCESS)
      return retval;
  }
  // Sort the datastructures.
  if(!linktablesorted()) {
     sortlinktable();
  }

  // Fill in trace, point and rpoint.
  fillintrace();
  makepointtable();

  return network::SUCCESS;
}

int network::readnodes(std::ifstream &netfile) {
  std::string line, name;
  double xcoord, ycoord;
  bool validline;
 
  while(netfile.good())  {
    validline = readline(netfile, line);
    if(!validline)
      continue;
    if(line[0] == ')')
      return SUCCESS;
    name = line.substr(0, line.find_first_of(' '));
    nodeid.push_back(name);
    nodenr[name] = nodeid.size()-1;
    
    // Get coordinates.
    line = line.substr(line.find_first_of('(')+2, line.find_first_of(')')-line.find_first_of(')')-1);
    std::istringstream ss(line);
    ss >> xcoord;
    ss >> ycoord;
    nodecoordinates.push_back(std::make_pair(xcoord, ycoord));
  }
  return PARSE_ERROR; // If the program ends up here, the ending parenthesis ) has not occured.
}

/* readlinks, reads a link line:
link_id  
      ( source_id  target_id ) 
      preinstalled_cap preinstalled_cost routing_cost  setup_cost  
      ( capacity_cost_list )  
      ( link_options )
*/
int network::readlinks(std::ifstream &netfile) {
  std::string line;
  bool validline;
  double cost, capacity;

  while(netfile.good()) {
    validline = readline(netfile, line);
    if(!validline)
      continue;
    if(line[0] == ')')
      return SUCCESS;
    
    std::string tail, head, cap_cost, inst_cap;
    
    int nodes_start = line.find_first_of('(') + 2;
    int nodes_end = line.find_first_of(')') - 2;
    int cap_start = nodes_end+4;
    int cap_end = line.find_first_of('(', cap_start)-2;
    int inst_start = cap_end+4;
    int inst_end = line.find_first_of(')', inst_start)-2;
    
    linkid.push_back(line.substr(0,nodes_start-3));
    linknr[line.substr(0, nodes_start-3)] = linkid.size()-1;

    tail = line.substr(nodes_start, nodes_end-nodes_start+1);
    head = tail.substr(tail.find_first_of(' ')+1, tail.size()-tail.find_first_of(' ')+1);
    tail = tail.substr(0, tail.find_first_of(' '));
    cap_cost = line.substr(cap_start, cap_end-cap_start);
    inst_cap = line.substr(inst_start, inst_end-inst_start);

    std::vector<int> linktablerow(3,0);
    std::vector<double> capacitytablerow(2,0);
    linktablerow[LINKTABLE_TAIL] = nodenr[tail];
    linktablerow[LINKTABLE_HEAD] = nodenr[head];
    linktablerow[LINKTABLE_TRACE] = NOT_DEFINED;

    std::istringstream ss(cap_cost);
    ss >> capacity;
    ss >> cost; // This is really the cost for the preinstallation, throw away.
    ss >> cost; // THIS is the cost per flow unit.
    capacitytablerow[CAPTABLE_COST] = cost;
    capacitytablerow[CAPTABLE_CAP] = capacity;

    std::istringstream ss2(inst_cap);
    while(ss2.good()) {
      ss2 >> capacity;
      ss2 >> cost; // This is now cost per INSTALLATION of extra modules.
      capacitytablerow.push_back(capacity);
      capacitytablerow.push_back(cost);
    }
    linktable.push_back(linktablerow);
    capacitytable.push_back(capacitytablerow);
  }
  return PARSE_ERROR;
}

int network::readdemands(std::ifstream &netfile) {
  bool validline;
  std::string from, to, line;
  int begin, end;
  double cdemand, units;

  demands = std::vector< std::vector <double> >(nodeid.size(), std::vector<double>(nodeid.size(), 0));

  while(netfile.good()) {
    validline = readline(netfile, line);
    if(!validline)
      continue;
    if(line[0] == ')')
      return SUCCESS;
    
    begin = line.find_first_of('(')+2;
    end = line.find_first_of(')');
    from = line.substr(begin, end-begin);
    to = from.substr(from.find_first_of(' ')+1, from.find_last_of(' ')-from.find_first_of(' ')-1);
    from = from.substr(0, from.find_first_of(' '));

    line = line.substr(end+1, line.size()-end);
    std::istringstream ss(line);
    ss >> units;
    ss >> cdemand;
    cdemand = cdemand * units;

    demands[nodenr[from]][nodenr[to]] = cdemand;
  }
  
  return PARSE_ERROR;
}

void network::makepointtable() {
  unsigned int ii;
  unsigned int tail, trace;
  std::vector< std::vector<int> >().swap(point);
  point = std::vector< std::vector<int> > (nodeid.size(), std::vector<int>(2, DOES_NOT_EXIST));
  for(ii = 0; ii < linktable.size(); ii++) {
    tail = linktable[ii][LINKTABLE_TAIL];
    trace = linktable[ii][LINKTABLE_TRACE];
    if(point[tail][POINT_POINT] == DOES_NOT_EXIST)
      point[tail][POINT_POINT] = ii;
    if(point[linktable[trace][LINKTABLE_HEAD]][POINT_RPOINT] 
       == DOES_NOT_EXIST)
      point[linktable[trace][LINKTABLE_HEAD]][POINT_RPOINT] = ii;
  }
  return;
}

void network::fillintrace() {
  unsigned int ii, jj, trace_to_fill_in = 0;
  for(ii = 0; ii < nodeid.size(); ii++) {
    for(jj = 0; jj < linktable.size(); jj++) {
      if((unsigned)linktable[jj][LINKTABLE_HEAD] == ii)
	linktable[trace_to_fill_in++][LINKTABLE_TRACE] = jj;
    }
  }
  return;
}

int network::read_solution_file(std::string path) {
  int retval;
  std::ifstream solfile;
  solfile.open(path.data(), std::ifstream::in);
  retval = read_solution_file(solfile);
  solfile.close();
  return retval;
}


int network::read_solution_file(std::ifstream &solfile) {
  std::string line;
  bool validline;

  if(!solfile.is_open()) {
    return FILE_NOT_OPEN;
  }
  getline(solfile, line);
  if(line.substr(0,53).compare("?SNDlib native format; type: solution; version: 1.0") != 0) {
    return FILE_NOT_VALID;
  }

  // Repeat until "LINK-CONFIGURATIONS" is found.
  while(solfile.good()) {
    validline = readline(solfile, line);
    if(!validline)
      continue;
    if(line[0] == ')')
      return PARSE_ERROR;
    if(line.substr(0, 21).compare("LINK-CONFIGURATIONS (") == 0)
      break;
  }
  
  while(solfile.good()) {
    validline = readline(solfile, line);
    if(!validline)
      continue;
    if(line[0] == ')')
      return SUCCESS;

    std::string linkname;
    int startpar, endpar;
    double cap, number, sum=0;

    startpar = line.find_first_of('(');
    endpar = line.find_first_of(')');
    linkname = line.substr(0, startpar - 1);
    
    std::istringstream ss(line.substr(startpar+2, endpar-startpar-3));
    while(ss.good()) {
      ss >> cap;
      ss >> number;
      sum += number*cap;
    }

    capacitytable[linknr[linkname]][CAPTABLE_CAP] = sum;
  }
  return PARSE_ERROR;
}



/* SORTING MEMBER FUNCTIONS */

bool network::linktablesorted() const {
  unsigned int ii;
  int maxtail, maxhead;
  maxtail = linktable[0][LINKTABLE_TAIL];
  maxhead = linktable[0][LINKTABLE_HEAD];
  for(ii = 1; ii < linktable.size(); ii++) {
    if(maxtail == linktable[ii][LINKTABLE_TAIL] && maxhead < linktable[ii][LINKTABLE_HEAD]) {
      maxhead = linktable[ii][LINKTABLE_HEAD];
      continue;
    }
    if(maxtail < linktable[ii][LINKTABLE_HEAD]) {
      maxhead = linktable[ii][LINKTABLE_HEAD];
      maxtail = linktable[ii][LINKTABLE_TAIL];
      continue;
    }
    return false;
  }
  return true;
}

void network::sortlinktable() {
  bool swapped = true;
  while(swapped) {
    swapped = false;
    for(int i = 1; i < linktable.size(); i++) {
      if( (linktable[i-1][LINKTABLE_TAIL] > linktable[i][LINKTABLE_TAIL]) ||
	 (linktable[i-1][LINKTABLE_TAIL] == linktable[i][LINKTABLE_TAIL] && 
	  linktable[i-1][LINKTABLE_HEAD] > linktable[i][LINKTABLE_HEAD])) {
	interchange_links(i-1, i);
	swapped = true;
      }
    }
  }
  return;
}

void network::interchange_links(int i, int j) {
  linktable[i].swap(linktable[j]);
  capacitytable[i].swap(capacitytable[j]);
  linkid[i].swap(linkid[j]);
  int temp = linknr[linkid[i]];
  linknr[linkid[i]] = linknr[linkid[j]];
  linknr[linkid[j]] = temp;
  return;
}

void network::make_bidirected() {
  std::vector< std::vector<int> > newlink; 
  std::vector<double> temp_cap;
  std::stringstream ss (std::stringstream::in | std::stringstream::out);
  std::string temp_id;
  int temp_int = 0;

  newlink = linktable;
  for(int i = 0; i < newlink.size(); i++) {
    temp_int = newlink[i][LINKTABLE_HEAD];
    newlink[i][LINKTABLE_HEAD] = newlink[i][LINKTABLE_TAIL];
    newlink[i][LINKTABLE_TAIL] = temp_int;

    ss << linkid[i] << "R";
    ss >> temp_id;
    linkid.push_back(temp_id);
    linknr[temp_id] = linkid.size()-1;
    linktable.push_back(newlink[i]);
    capacitytable.push_back(capacitytable[i]);
  }
  
  sortlinktable();
  fillintrace();
  makepointtable();

  return;
}


/* DATA ACCESS MEMBER FUNCTIONS */

std::vector<int> network::linktablerow(unsigned int rownumber) {
  if(rownumber >= linktable.size())
    return std::vector<int>(0);
  std::vector<int> row = linktable[rownumber];
  return row;
}

std::vector<double> network::capacitytablerow(unsigned int rownumber) {
  if(rownumber >= capacitytable.size())
    return std::vector<double>(0);
  std::vector<double> row = capacitytable[rownumber];
  return row;
}

std::vector<int> network::pointrow(unsigned int rownumber) {
  if(rownumber >= point.size())
    return std::vector<int>(0);
  std::vector<int> row = point[rownumber];
  return row;
}

unsigned int network::linktablerows() const {
  return linktable.size();
}

double network::demand(unsigned int from, unsigned int to) const {
  if(from >= demands.size() || to > demands[from].size())
    return (double)DOES_NOT_EXIST;
  return demands[from][to];
}

double network::demand(unsigned int to) const {
  unsigned int i;
  double sum = 0;
  for(i = 0; i < demands.size(); i++) {
    if(to < demands[i].size())
      sum += demands[i][to];
  }
  return sum;
}

bool network::demand_to_node(unsigned int to) const {
  for(int i = 0; i < demands.size(); i++) {
    if( demands[i][to] != 0)
      return true;
  }
  return false;
}

unsigned int network::nodes_with_nonzerodemands() const {
  unsigned int sum = 0;
  for(unsigned int i = 0; i < demands.size(); i++) {
    if(demand_to_node(i))
      sum++;
  }
  return sum;
}

int network::nonzero_demand_node_index(unsigned int nodenr) const {
  if(!demand_to_node(nodenr))
    return DOES_NOT_EXIST;
  unsigned int sum = 0;
  for(unsigned int i = 0; i < nodenr; i++) {
    if(demand_to_node(i))
      sum++;
  }
  return sum;
}

int network::nonzero_demand_node_from_index(unsigned int index) const {
  unsigned int sum = 0;
  unsigned int i;
  for(i = 0; i < point.size(); i++) {
    if(demand_to_node(i)) {
      if(sum == index)
	return i;
      sum++;
    }
  }
  if(sum == index)
    return i;
  return DOES_NOT_EXIST;
}

int network::get_demand_index(unsigned int from, unsigned int to) const {
  unsigned int i, j, sum = 0;
  if(demands[from][to] == 0)
    return DOES_NOT_EXIST;
  for(i = 0; i < from; i++) {
    for(j = 0; j < demands[i].size(); j++) {
      if(demands[i][j] != 0)
	sum++;
    }
  }
  for(j = 0; j < to; j++) {
    if(demands[from][j] != 0)
      sum++;
  }
  return sum;
}

double network::get_demand_from_index(unsigned int index) const {
  unsigned int i, j, sum = 0;

  for(i = 0; i < demands.size(); i++) {
    for(j = 0; j < demands.size(); j++) {
      if(demands[i][j] != 0) {
	if(index == sum)
	  return demands[i][j];
	sum++;
      }
    }
  }
  return (double)DOES_NOT_EXIST;
}

std::vector<int> network::get_fromto_from_index(unsigned int index) const {
  std::vector<int> vec(2, DOES_NOT_EXIST);
  
  unsigned int i, j, sum = 0;
  for(i = 0; i < demands.size(); i++) {
    for(j = 0; j < demands[i].size(); j++) {
      if(demands[i][j] != 0){
	if(index == sum) {
	  vec[0] = i;
	  vec[1] = j;
	  return vec;
	}
	sum++;
      }
    }
  }
  return vec;
}


int network::get_link_nr(unsigned int from, unsigned int to) const {
  if(from >= nodeid.size() || to >= nodeid.size())
    return DOES_NOT_EXIST;
  int ii = point[from][POINT_POINT];
  if(ii == -1)
    return DOES_NOT_EXIST;
  for(; ii < (signed)linktable.size(); ii++) {
    if(linktable[ii][LINKTABLE_TAIL] != (signed)from) {
      return DOES_NOT_EXIST;
    }
    else if(linktable[ii][LINKTABLE_HEAD] == (signed)to) {
      return ii;
    }
  }
  return DOES_NOT_EXIST;
}

int network::get_reverse_link_nr(int linknr) const {
  if(linknr > linktable.size())
    return DOES_NOT_EXIST;
  int reversehead = linktable[linknr][LINKTABLE_TAIL], reversetail = linktable[linknr][LINKTABLE_HEAD];
  int i = point[reversetail][POINT_POINT];
  while(linktable[i][LINKTABLE_TAIL] == reversetail) {
    if(linktable[i][LINKTABLE_HEAD] == reversehead)
      return i;
    i++;
  }
  return DOES_NOT_EXIST;
}

std::pair<double, double> network::get_node_coordinates(unsigned int nodenr) {
  if(nodenr > nodecoordinates.size())
    return std::make_pair((double)DOES_NOT_EXIST, (double)DOES_NOT_EXIST);
  return nodecoordinates[nodenr];
}

unsigned int network::nodes() const {
  return nodeid.size();
}

unsigned int network::nonzerodemands() const {
  unsigned int i, j, sum = 0;
  for(i = 0; i < demands.size(); i++) {
    for(j = 0; j < demands[i].size(); j++) {
      if(demands[i][j] != 0)
	sum++;
    }
  }
  return sum;
}

unsigned int network::nonzerodemands(unsigned int to) const {
  unsigned int i, sum = 0;
  for(i = 0; i < demands.size(); i++) {
    if(to < demands[i].size() && demands[i][to] != 0)
      sum++;
  }
  return sum;
}

// const_iterators for reading the tables directly
std::vector< std::vector<int> >::const_iterator network::point_begin() {
  return point.begin();
}

std::vector< std::vector<int> >::const_iterator network::point_end() {
  return point.end();
}

std::vector< std::vector<int> >::const_iterator network::linktable_begin() {
  return linktable.begin();
}

std::vector< std::vector<int> >::const_iterator network::linktable_end() {
  return linktable.end();
}

std::vector< std::vector<double> >::const_iterator network::capacitytable_begin() {
  return capacitytable.begin();
}

std::vector< std::vector<double> >::const_iterator network::capacitytable_end() {
  return capacitytable.end();
}

// MISC DATA ASSIGNMENT MEMBER FUNCTIONS

void network::assign_random_link_costs(int min, int max) {
  unsigned int ii;

  if(min <= 0 || max < min || max < 1)
    return;
  srand((unsigned)time(0));
  
  for(ii = 0; ii < linktable.size(); ii++) {
    if(capacitytable[ii][CAPTABLE_COST] == 0) 
      capacitytable[ii][CAPTABLE_COST] = (double)((rand() % (max-min)) + min+1);
  }
}

int network::assign_capacities(std::vector<double> caps) {
  for(int i = 0; i < caps.size() && i < capacitytable.size(); i++)
    capacitytable[i][network::CAPTABLE_CAP] = caps[i];
  return SUCCESS;
}
